1990C - Mad MAD Sum - CodeForces Solution

t=int(input())
result=[]
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    if(n==1):
        result.append("1")
        continue
    my_set=set()
    sums=sum(a)
    max_sim=0
    my_set.add(a[0])
    b=[0]*n 
    count=1
    for i in a[1:]:
        if(i in my_set):
            max_sim=max(max_sim,i)
        else:
            my_set.add(i)
        b[count]=max_sim
        count+=1
    if(set(b)=={0}):
        result.append(str(sums))
        continue
    sums+=sum(b)
    my_set=set([b[0]])
    max_sim=0
    bro=[0]*n
    count=1
    for i in b[1:]:
        if(i in my_set):
            if(i>max_sim):
                max_sim=i
        else:
            my_set.add(i)
        bro[count]=max_sim
        count+=1
    if(set(bro)=={0}):
        result.append(str(sums))
        continue
    for i in range(n):
        if(bro[n-1-i]==0):
            break
        sums+=bro[n-1-i]*(i+1)
    result.append(str(sums))
    
    
print("\n".join(result))